package leetcode_day._2021._202112._1120;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/20 17:46
 * 供暖气
 * 季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
 * 在加热器的加热半径范围内的每个房屋都可以获得供暖。
 * 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
 * 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
 * 算法：排序 + 贪心
 * 对于每个房屋，要么用前面的暖气，要么用后面的暖气，二者取近的，得到距离
 * 对于所有的房屋，取最大的上述距离
 */
public class _20_475 {

    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int ans = 0;
        int n = heaters.length;
        int i = 0;
        for (int house : houses) {
            while (i < n && house > heaters[i]) ++i;
            if (i == 0) ans = Math.max(ans, heaters[i] - house);
            else if (i == n) ans = Math.max(ans, house - heaters[n - 1]);
            else ans = Math.max(ans, Math.min(house - heaters[i - 1], heaters[i] - house));
        }
        return ans;
    }

}
